package mao.leetcode.array.leetcode34;

public class Solution {

    public int[] searchRange(int[] nums, int target) {
        int[] ans={-1,-1};
        if (nums == null || nums.length == 0) return ans;
        int left = binarySearchLeft(nums, target );
        int right = binarySearchRight(nums, target);
        if (right < left)
            return ans;
        else {
            ans[0]=left;
            ans[1]=right;
        }
        return ans;
    }

    public static int binarySearchLeft(int[] nums, int target){
        int start=0,end=nums.length-1;
        while (start <=  end){
            int mid=start+(end-start)/2;
            if (nums[mid] >= target)
                end=mid-1;
            else
                start=mid+1;
        }
        return  end+1; //如果找不到，返回刚好大于这个数的，
    }

    public static int binarySearchRight(int[] nums, int target){
        int start=0,end=nums.length-1;
        while (start <=  end){
            int mid=start+(end-start)/2;
            if (nums[mid] <= target)
                start=mid+1;
            else
                end=mid-1;
        }
        return  start-1; //如果找不到，返回刚好大于这个数的，
    }
}
